package kLengthApart;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        // 思路 把所有1的位置用集合记录下来 再看他们任意两个元素之间的插值是不是大于等于k
//        List<Integer>list = new ArrayList<>();
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i]==1){
//                list.add(i);
//            }
//        }
//        for (int i = 0; i < list.size(); i++) {
//            for (int j = i+1; j < list.size(); j++) {
//                if(Math.abs(list.get(i)-list.get(j)) < k+1){
//                    return false;
//                }
//            }
//        }
//        return true;

        // 思路 双指针 每次遍历到1的时候就和前一个1的位置比较
        int l = 0;
        int r = 0;
        while (l<nums.length&&r<nums.length){
            while (l<nums.length&&nums[l]==0){
                l++;
            }
            r = l+1;
            while (r<nums.length&&nums[r]==0){
                r++;
            }
            if(l<nums.length&&r<nums.length){
                if(nums[r] ==1&&nums[l] == 1){
                    if( r-l-1  < k ){
                        return false;
                    }
                    l = r;
                    r++;
                }
            }
        }
        return true;
    }
}
//class Solution {
//    public boolean kLengthApart(int[] nums, int k) {
//        int n = nums.length;
//        int prev = -1;
//        for (int i = 0; i < n; ++i) {
//            if (nums[i] == 1) {
//                if (prev != -1 && i - prev - 1 < k) {
//                    return false;
//                }
//                prev = i;
//            }
//        }
//        return true;
//    }
//}
